﻿/*
OJ 
Time Limit:1000MS  Memory Limit:32768K

  
Description:
大写字母与数字的映射关系如下表所示： ADGJMPSVY 1 2 3 BEHKNQTWZ 4 5 6 CFILORUX 7 8 9 
说明字母A可以表示数字1，也可以表示数字2和3。
其他同理。给出一个由2个大写字母表示的字符串，请找出其能够表示的最小素数。如果不存在，请输出-1。 

Input:
输入数据有N组。每组测试数据由一个包含2个大写字母的字符串组成。 
Output:
输出数据有N行，每行表示一组测试数据的输出结果。 
Sample Input:
1
OJ
Sample Output:
71
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int digits[][3]={
	{1, 2, 3},
	{4, 5, 6},
	{7, 8, 9}
};
static char* alphas[]={
"ADGJMPSVY",
"BEHKNQTWZ",
"CFILORUX"
};

static const int primes[]={
11,13,17,19,23,29,31,
37,41,43,47,53,59,61,
67,71,73,79,83,89,97
};

int main()
{
	unsigned n;
	scanf("%u", &n);
	getchar();
	while (n--)
	{
		char str[2];
		int* maps[2];

		gets(str);
		{
			for (unsigned k=0;str[k]; k++)
			{
				unsigned i=0;
				for (; i<3 && NULL==strchr(alphas[i], str[k]); i++);
			
				if(i!=3)
					maps[k]=digits[i];
			}
		}
		bool found=false;
		for (unsigned k=0; k<3; k++ )
		{
			for (unsigned i=0; i<3; i++ )
			{
				unsigned num=maps[0][k]*10+maps[1][i];
				if(binary_search(primes, primes+21, num))
				{
					found=true;
					printf("%u\n", num);
					break;
				}
			}
			if(found)
				break;
		}
		if(!found)
			printf("-1\n");
	}
	return EXIT_SUCCESS;
}